package mycollections;

import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {

	public static <T> void swap(MyList<T> list, int i, int j) {
		T temp = list.get(i);
		list.set(i, list.get(j));
		list.set(j, temp);
	}
	
	public static <T> void copy(MyList<T> dest, MyList<? extends T> src) {
		dest.addAll((T[]) src.toArray());		
	}
	
	public static <T> void reverse(MyList<T> list) {		
			for(int i = 0, mid = list.size()/2, j = list.size()-1;i < mid; i++, j--) {
				swap(list,i,j);
			}
	}
	
	public static <T extends Comparable<T>> int binarySearch(MyList<T> list, T key) {
		int low = 0;
		int high = list.size() - 1;
		while(low <= high) {
			int mid = (low + high)/2;
			Comparable<T> midVal = list.get(mid);
			int cmp = midVal.compareTo(key);
			if(cmp < 0)
				low = mid + 1;
			else if(cmp > 0)
				high = mid - 1;
			else
				return mid;			
		}
		return -(low + 1);
	}
	
	public static <T extends Comparable<T>> void sort(MyList<T> list) {		
		Comparator<T> comp = new Comparator<T>(){
			public int compare(T obj1, T obj2) {
				return obj1.compareTo(obj2);
			}
		};
		if (list instanceof RandomAccess) {
			qSort(list, comp);
		} else {
			bubbleSort(list,comp);
		}
	}
	
	public static <T extends Comparable<T>> void sort(MyList<T> list, Comparator<T> comp) {
		if (list instanceof RandomAccess) {
			qSort(list, comp);
		} else {
			bubbleSort(list,comp);
		}
	}

	private static <T extends Comparable<T>> void bubbleSort(
			MyList<T> list, Comparator<? super T> comp) {
		int j;
		boolean flag = true;
		T temp;
		while (flag) {
			flag = false;
			for (j = 0; j < list.size() - 1; j++) {
				if (comp.compare(list.get(j), list.get(j + 1)) > 0) {
					temp = list.get(j);
					list.set(j, list.get(j + 1));
					list.set(j + 1, temp);
					flag = true;
				}
			}
		}
	}

	private static <T extends Comparable<T>> void qSort(MyList<T> list, Comparator<T> comp) {
		if (list == null || list.size() == 0) {
			return;
		}
		quicksort(list, comp, 0, list.size() - 1);
	}

	private static <T extends Comparable<T>> void quicksort(
			MyList<T> list, Comparator<T> comp, int low, int high) {
		int i = low, j = high;
		T pivot = list.get(low + (high - low) / 2);
		while (i <= j) {
			while (comp.compare(list.get(i), pivot) < 0) {
				i++;
			}
			while (comp.compare(list.get(j), pivot) > 0) {
				j--;
			}
			if (i <= j) {
				T temp = list.get(i);
				list.set(i, list.get(j));
				list.set(j, temp);
				i++;
				j--;
			}
		}
		if (low < j)
			quicksort(list, comp, low, j);
		if (i < high)
			quicksort(list, comp, i, high);
	}

}
